Huffman coding is a loss-less compression technique often used in lossy compression schemes as the final step after decomposition and quantization of a signal. Huffman coding uses unique variable length code words and no Huffman code is a prefix of another Huffman code. For a given probability density function of a symbol set, shorter codes can be assigned to frequently occurring symbols while longer codes can be assigned to less frequently occurring symbols. Huffman's minimum redundancy encoding minimizes the average number of bits required to represent the data and is one type of variable length coding.
Huffman coding is useful for reduction of the bit-rate by exploring statistical redundancies and to encode a “minimum set” of information using entropy-coding technique. Usually entropy coders exploit the symbol probabilities independent of the previous symbols, and hence are optimal for uncorrelated sequences.
The Huffman coding/decoding is one of the key components of an encoder/decoder in many of the audio/video compression standards. So there is a necessity of its implementation on the digital signal processor (DSP) for a cost effective solution. However, the architecture and instruction set of DSPs are optimized for computations with operands that are byte, half word or word size. Since the symbols have variable length after encoding, there is a necessity of extracting code words that are not necessarily byte, half word, or word size.
On the other hand, the memory access usually fetches data that are only byte, half word, or word aligned. Due to this, the speed of the Huffman Decoder implemented on DSP is lower than that of a corresponding implementation on dedicated hardware.
In addition to this, most of the compression standards have multiple Huffman tables containing long code words that have to be stored on expensive on-chip memory for fast access. These two factors emphasize the importance of high speed and memory efficient implementation of Huffman decoding on the DSP. Though the DSP's architectures are optimized for for signal processing applications, they are not so in the case of search algorithms.
Given that Huffman encoding/decoding is a very important component of compression standards, it is important that the Huffman Encoder/Decoder should be efficiently implemented on the DSP chosen. The complexity of the Huffman decoder's implementation lies in fast search of the symbol encoded from the bit-stream without consuming large memory. These two requirements are conflicting and in addition, the standards have multiple tables of large code length.
Further limitations and disadvantages of conventional and traditional systems will become apparent to one of skill in the art through comparison of such systems with the invention as set forth in the remainder of the present application with reference to the drawings.